Fizz Buzz Multithreaded

Posted on |

问题描述（难度中等-1195）

Write a program that outputs the string representation of numbers from 1 to n, however:

  • If the number is divisible by 3, output “fizz”.
  • If the number is divisible by 5, output “buzz”.
  • If the number is divisible by both 3 and 5, output “fizzbuzz”.

For example, for n = 15, we output: 1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz.

Suppose you are given the following code:

1
2
3
4
5
6
7
class FizzBuzz {
  public FizzBuzz(int n) { ... }               // constructor
  public void fizz(printFizz) { ... }          // only output "fizz"
  public void buzz(printBuzz) { ... }          // only output "buzz"
  public void fizzbuzz(printFizzBuzz) { ... }  // only output "fizzbuzz"
  public void number(printNumber) { ... }      // only output the numbers
}

Implement a multithreaded version of FizzBuzz with four threads. The same instance of FizzBuzz will be passed to four different threads:

  1. Thread A will call fizz() to check for divisibility of 3 and outputs fizz.
  2. Thread B will call buzz() to check for divisibility of 5 and outputs buzz.
  3. Thread C will call fizzbuzz() to check for divisibility of 3 and 5 and outputs fizzbuzz.
  4. Thread D will call number() which should only output the numbers.

方法一：using volatile

通过定义volatile变量flag，以循环自检的方式执行。这里总结下这种方法的通用范式：

1
2
3
4
5
6
while(trure){
  //条件1 条件必须唯一
  if(flag){...update flag}
  //条件2 条件必须唯一
  if(flag){...update flag}
}

上面的范式可以通用，但是可能会导致TLP问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
package P1195;

import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.function.IntConsumer;

/**
 * @autor yeqiaozhu.
 * @date 2019-10-04
 */
public class UsingVolatile {
    private int n;
    private volatile int currentValue=1;

    public UsingVolatile(int n) {
        this.n = n;
    }

    // printFizz.run() outputs "fizz".
    public void fizz(Runnable printFizz) throws InterruptedException {
        while (true){
            if(currentValue<=n && currentValue%3==0 && currentValue%15!=0) {
                //执行打印fizz代码
                printFizz.run();
                ++currentValue;
            }
            Thread.sleep(1);
        }
    }

    // printBuzz.run() outputs "buzz".
    public void buzz(Runnable printBuzz) throws InterruptedException {
        while (true){
            if(currentValue<=n && currentValue % 5== 0 && currentValue % 15 != 0) {
                printBuzz.run();
                ++currentValue;
            }
            Thread.sleep(1);
        }
    }

    // printFizzBuzz.run() outputs "fizzbuzz".
    public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
        while (true){
            if(currentValue<=n && currentValue % 15==0){
                printFizzBuzz.run();
                ++currentValue;
            }
            Thread.sleep(1);
        }
    }

    // printNumber.accept(x) outputs "x", where x is an integer.
    public void number(IntConsumer printNumber) throws InterruptedException {
        while (true){
            if(currentValue%3!=0 && currentValue % 5!=0){
                printNumber.accept(currentValue);
                ++currentValue;
            }
            Thread.sleep(1);
        }
    }

    public static void main(String[] args) {
        Queue<String> strings = new LinkedBlockingQueue<>();

        FizzBuzz fizzBuzz = new FizzBuzz(16);

        Thread t1, t2, t3, t4;

        (t1 = new Thread(() -> {
            try {
                fizzBuzz.fizz(() -> strings.add("fizz"));
            } catch (InterruptedException e) {
                System.err.println(e.toString());
                Thread.currentThread().interrupt();
            }
        })).start();

        (t2 = new Thread(() -> {
            try {
                fizzBuzz.buzz(() -> strings.add("buzz"));
            } catch (InterruptedException e) {
                System.err.println(e.toString());
                Thread.currentThread().interrupt();
            }
        })).start();

        (t3 = new Thread(() -> {
            try {
                fizzBuzz.fizzbuzz(() -> strings.add("fizzbuzz"));
            } catch (InterruptedException e) {
                System.err.println(e.toString());
                Thread.currentThread().interrupt();
            }
        })).start();

        (t4 = new Thread(() -> {
            try {
                fizzBuzz.number(number -> strings.add("" + number));
            } catch (InterruptedException e) {
                System.err.println(e.toString());
                Thread.currentThread().interrupt();
            }
        })).start();


        try {
            t3.join();
            t4.join();
            t2.join();
            t1.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println();
    }
}

方法二：using synchronized

通过对象提供的基本操作等待/通知范式，等待通知需要定义两个基本操作一个生产一个消费：

1
2
3
4
5
6
7
8
9
10
private void consumer(){
  synchoronized(object){
    while(flag){
      object.wait();
    }
    //执行消费过程 例如打印一个b 检查生产的标志变量是否已经生产完成
    system.out.println("b");
    flag=false;
  }
}
1
2
3
4
5
6
7
private void producer(){
  synchornized(object){
    //执行生产动作 例如打印一个a 同时将变量修改为已生产
 		system.out.println("a");
    object.notifyAll();
  }
}

如果要进行范式的循环，在范式外面加一层循环，于是范式演变成：

1
2
3
4
5
6
7
8
9
10
11
12
13
private void consumer(){
  //执行循环的次数 不断进行消费
  for(int i=0;i<n;i++){
        synchoronized(object){
        while(flag){
        object.wait();
        }
       //执行消费过程 例如打印一个b
       system.out.println("b");
       flag=false;
  	 }
  }
}

利用上面的范式，我们可以看到关键是要确定两步：

  • 1.循环次数
  • 2.变量的等待条件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package P1195;
import java.util.function.IntConsumer;

class FizzBuzz {
    private int n;
    private int currentValue=1;

    public FizzBuzz(int n) {
        this.n = n;
    }

    // printFizz.run() outputs "fizz".
    public void fizz(Runnable printFizz) throws InterruptedException {
        for (int i = 0; i < n/3-n/15; i++) {
            synchronized (FizzBuzz.class){
                while(currentValue%3!=0 || currentValue%15==0){
                    FizzBuzz.class.wait();
                }
                //执行打印fizz代码
                printFizz.run();
                currentValue++;
                FizzBuzz.class.notifyAll();
            }
        }
    }

    // printBuzz.run() outputs "buzz".
    public void buzz(Runnable printBuzz) throws InterruptedException {
        for (int i = 0; i < n/5-n/15; i++) {
            synchronized (FizzBuzz.class){
                while (currentValue%5!=0 || currentValue%15==0){
                    FizzBuzz.class.wait();
                }
                printBuzz.run();
                currentValue++;
                FizzBuzz.class.notifyAll();
            }
        }
    }

    // printFizzBuzz.run() outputs "fizzbuzz".
    public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
        for (int i = 0; i < n/15; i++) {
            synchronized (FizzBuzz.class){
                while (currentValue%15!=0){
                    FizzBuzz.class.wait();
                }
                printFizzBuzz.run();
                currentValue++;
                FizzBuzz.class.notifyAll();
            }
        }
    }

    // printNumber.accept(x) outputs "x", where x is an integer.
    public void number(IntConsumer printNumber) throws InterruptedException {
        for (int i = 0; i < (n-n/3-n/5+n/15); i++) {
            synchronized (FizzBuzz.class){
                while (currentValue%5==0 || currentValue%3==0){
                    FizzBuzz.class.wait();
                }
                printNumber.accept(currentValue);
                currentValue++;
                FizzBuzz.class.notifyAll();
            }
        }
    }
}

方法三：using lock

这里维护多个等待队列貌似没有意义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
package P1195;

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.IntConsumer;

/**
 * @autor yeqiaozhu.
 * @date 2019-10-04
 */
public class UsingLockCondition {
    private int n;
    private int currentValue=1;

    ReentrantLock reentrantLock=new ReentrantLock();

    Condition condition=reentrantLock.newCondition();

    public UsingLockCondition(int n) {
        this.n = n;
    }

    // printFizz.run() outputs "fizz".
    public void fizz(Runnable printFizz) throws InterruptedException {
        for (int i = 0; i < n/3-n/15; i++) {
            reentrantLock.lock();
            while(currentValue%3!=0 || currentValue%15==0){
                condition.await();
            }
            //执行打印fizz代码
            printFizz.run();
            currentValue++;
            condition.signalAll();
            reentrantLock.unlock();
        }
    }

    // printBuzz.run() outputs "buzz".
    public void buzz(Runnable printBuzz) throws InterruptedException {
        for (int i = 0; i < n/5-n/15; i++) {
            reentrantLock.lock();
            while (currentValue%5!=0 || currentValue%15==0){
                condition.await();
            }
            printBuzz.run();
            currentValue++;
            condition.signalAll();
            reentrantLock.unlock();
        }
    }

    // printFizzBuzz.run() outputs "fizzbuzz".
    public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
        for (int i = 0; i < n/15; i++) {
            reentrantLock.lock();
            while (currentValue%15!=0){
                condition.await();
            }
            printFizzBuzz.run();
            currentValue++;
            condition.signalAll();
            reentrantLock.unlock();
        }
    }

    // printNumber.accept(x) outputs "x", where x is an integer.
    public void number(IntConsumer printNumber) throws InterruptedException {
        for (int i = 0; i < (n-n/3-n/5+n/15); i++) {
            reentrantLock.lock();
            while (currentValue%5==0 || currentValue%3==0){
                condition.await();
            }
            printNumber.accept(currentValue);
            currentValue++;
            condition.signalAll();
            reentrantLock.unlock();
        }
    }
}

方法四：using atomic

利用atomic提供的封装函数，实际上利用cas实现原子写操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.ConcurrentModificationException;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.IntConsumer;

class FizzBuzz {

    private final AtomicInteger counter;

    private final int n;

    public FizzBuzz(int n) {
        this.n = n;
        counter = new AtomicInteger(1);
    }

    private void updateToNext(int count) {
        if (!counter.compareAndSet(count, count + 1))
            throw new ConcurrentModificationException();
    }

    public void fizz(Runnable printFizz) throws InterruptedException {
        int count;
        while ((count = counter.get()) <= n) {
            if (count % 3 == 0 && count % 5 != 0) {
                printFizz.run();
                updateToNext(count);
            }
        }
    }

    public void buzz(Runnable printBuzz) throws InterruptedException {
        int count;
        while ((count = counter.get()) <= n) {
            if (count % 3 != 0 && count % 5 == 0) {
                printBuzz.run();
                updateToNext(count);
            }
        }
    }

    public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
        int count;
        while ((count = counter.get()) <= n) {
            if (count % 3 == 0 && count % 5 == 0) {
                printFizzBuzz.run();
                updateToNext(count);
            }
        }
    }

    public void number(IntConsumer printNumber) throws InterruptedException {
        int count;
        while ((count = counter.get()) <= n) {
            if (count % 3 != 0 && count % 5 != 0) {
                printNumber.accept(count);
                updateToNext(count);
            }
        }
    }
}

总结

通过循环自检或者等待通知的方式实现。